package com.fzkj.algorithm;

/**
 * 山脉数组的封顶索引
 */
public class Mutaion {
    /**
     * 题目描述
     * @param args
     */
    //    符合下列属性的数组 arr 称为 山脉数组 ：
    //    arr.length >= 3
    //    存在 i（0 < i < arr.length - 1）使得：
    //    arr[0] < arr[1] < ... arr[i-1] < arr[i]
    //    arr[i] > arr[i+1] > ... > arr[arr.length - 1]
    //    给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

    /**
     * 题目思路：
     * 由于给定了一个山脉数组，所以很容易就想到了双指针的方式
     * 找到一个下标，使其满足大于前一个和后一个元素即可。时间复杂度为O(n)。
     * 官方说还有O(log(n))的方式。
     * 但是看了看官方的答案，好像确实不需要用到双指针。。。
     *
     * 官方时间复杂度为O(log(n))的解法为二分查找，
     *
     * @param args
     */

    public static void main(String[] args) {
        int[] arr = {24, 69, 100, 99, 79, 78, 67, 36, 26, 19};
        solve(arr);
    }

    /**
     * 遍历的方式
     * @param arr
     */
//    private static void solve(int[] arr){
//        for (int i = 0; i < arr.length; i++) {
//            if (arr[i + 1] < arr[i]) {
//                System.out.println(i);
//                break;
//            }
//        }
//    }

    /**
     * 二分查找的方式
     */
    private static void solve(int[] arr){
        int n = arr.length;
        int left = 0, right = n - 1, ans = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }


}
